
%% bare_conf.tex
%% V1.4b
%% 2015/08/26
%% by Michael Shell
%% See:
%% http://www.michaelshell.org/
%% for current contact information.
%%
%% This is a skeleton file demonstrating the use of IEEEtran.cls
%% (requires IEEEtran.cls version 1.8b or later) with an IEEE
%% conference paper.
%%
%% Support sites:
%% http://www.michaelshell.org/tex/ieeetran/
%% http://www.ctan.org/pkg/ieeetran
%% and
%% http://www.ieee.org/

%%*************************************************************************
%% Legal Notice:
%% This code is offered as-is without any warranty either expressed or
%% implied; without even the implied warranty of MERCHANTABILITY or
%% FITNESS FOR A PARTICULAR PURPOSE!
%% User assumes all risk.
%% In no event shall the IEEE or any contributor to this code be liable for
%% any damages or losses, including, but not limited to, incidental,
%% consequential, or any other damages, resulting from the use or misuse
%% of any information contained here.
%%
%% All comments are the opinions of their respective authors and are not
%% necessarily endorsed by the IEEE.
%%
%% This work is distributed under the LaTeX Project Public License (LPPL)
%% ( http://www.latex-project.org/ ) version 1.3, and may be freely used,
%% distributed and modified. A copy of the LPPL, version 1.3, is included
%% in the base LaTeX documentation of all distributions of LaTeX released
%% 2003/12/01 or later.
%% Retain all contribution notices and credits.
%% ** Modified files should be clearly indicated as such, including  **
%% ** renaming them and changing author support contact information. **
%%*************************************************************************


% *** Authors should verify (and, if needed, correct) their LaTeX system  ***
% *** with the testflow diagnostic prior to trusting their LaTeX platform ***
% *** with production work. The IEEE's font choices and paper sizes can   ***
% *** trigger bugs that do not appear when using other class files.       ***                          ***
% The testflow support page is at:
% http://www.michaelshell.org/tex/testflow/



\documentclass[conference, 10pt]{IEEEtran}
% Some Computer Society conferences also require the compsoc mode option,
% but others use the standard conference format.
%
% If IEEEtran.cls has not been installed into the LaTeX system files,
% manually specify the path to it like:
% \documentclass[conference]{../sty/IEEEtran}





% Some very useful LaTeX packages include:
% (uncomment the ones you want to load)


% *** MISC UTILITY PACKAGES ***
%
%\usepackage{ifpdf}
% Heiko Oberdiek's ifpdf.sty is very useful if you need conditional
% compilation based on whether the output is pdf or dvi.
% usage:
% \ifpdf
%   % pdf code
% \else
%   % dvi code
% \fi
% The latest version of ifpdf.sty can be obtained from:
% http://www.ctan.org/pkg/ifpdf
% Also, note that IEEEtran.cls V1.7 and later provides a builtin
% \ifCLASSINFOpdf conditional that works the same way.
% When switching from latex to pdflatex and vice-versa, the compiler may
% have to be run twice to clear warning/error messages.






% *** CITATION PACKAGES ***
%
\usepackage{cite}
% cite.sty was written by Donald Arseneau
% V1.6 and later of IEEEtran pre-defines the format of the cite.sty package
% \cite{} output to follow that of the IEEE. Loading the cite package will
% result in citation numbers being automatically sorted and properly
% "compressed/ranged". e.g., [1], [9], [2], [7], [5], [6] without using
% cite.sty will become [1], [2], [5]--[7], [9] using cite.sty. cite.sty's
% \cite will automatically add leading space, if needed. Use cite.sty's
% noadjust option (cite.sty V3.8 and later) if you want to turn this off
% such as if a citation ever needs to be enclosed in parenthesis.
% cite.sty is already installed on most LaTeX systems. Be sure and use
% version 5.0 (2009-03-20) and later if using hyperref.sty.
% The latest version can be obtained at:
% http://www.ctan.org/pkg/cite
% The documentation is contained in the cite.sty file itself.






% *** GRAPHICS RELATED PACKAGES ***
%
\ifCLASSINFOpdf
  \usepackage[pdftex]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../pdf/}{../jpeg/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.pdf,.jpeg,.png}
\else
  % or other class option (dvipsone, dvipdf, if not using dvips). graphicx
  % will default to the driver specified in the system graphics.cfg if no
  % driver is specified.
  % \usepackage[dvips]{graphicx}
  % declare the path(s) where your graphic files are
  % \graphicspath{{../eps/}}
  % and their extensions so you won't have to specify these with
  % every instance of \includegraphics
  % \DeclareGraphicsExtensions{.eps}
\fi
% graphicx was written by David Carlisle and Sebastian Rahtz. It is
% required if you want graphics, photos, etc. graphicx.sty is already
% installed on most LaTeX systems. The latest version and documentation
% can be obtained at:
% http://www.ctan.org/pkg/graphicx
% Another good source of documentation is "Using Imported Graphics in
% LaTeX2e" by Keith Reckdahl which can be found at:
% http://www.ctan.org/pkg/epslatex
%
% latex, and pdflatex in dvi mode, support graphics in encapsulated
% postscript (.eps) format. pdflatex in pdf mode supports graphics
% in .pdf, .jpeg, .png and .mps (metapost) formats. Users should ensure
% that all non-photo figures use a vector format (.eps, .pdf, .mps) and
% not a bitmapped formats (.jpeg, .png). The IEEE frowns on bitmapped formats
% which can result in "jaggedy"/blurry rendering of lines and letters as
% well as large increases in file sizes.
%
% You can find documentation about the pdfTeX application at:
% http://www.tug.org/applications/pdftex





% *** MATH PACKAGES ***
%
\usepackage{amsmath, amsthm}
\newtheorem{theorem}{Theorem}
% A popular package from the American Mathematical Society that provides
% many useful and powerful commands for dealing with mathematics.
%
% Note that the amsmath package sets \interdisplaylinepenalty to 10000
% thus preventing page breaks from occurring within multiline equations. Use:
%\interdisplaylinepenalty=2500
% after loading amsmath to restore such page breaks as IEEEtran.cls normally
% does. amsmath.sty is already installed on most LaTeX systems. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/amsmath





% *** SPECIALIZED LIST PACKAGES ***
%
\usepackage{algorithm}
\usepackage{algorithmic}
% algorithmic.sty was written by Peter Williams and Rogerio Brito.
% This package provides an algorithmic environment fo describing algorithms.
% You can use the algorithmic environment in-text or within a figure
% environment to provide for a floating algorithm. Do NOT use the algorithm
% floating environment provided by algorithm.sty (by the same authors) or
% algorithm2e.sty (by Christophe Fiorio) as the IEEE does not use dedicated
% algorithm float types and packages that provide these will not provide
% correct IEEE style captions. The latest version and documentation of
% algorithmic.sty can be obtained at:
% http://www.ctan.org/pkg/algorithms
% Also of interest may be the (relatively newer and more customizable)
% algorithmicx.sty package by Szasz Janos:
% http://www.ctan.org/pkg/algorithmicx




% *** ALIGNMENT PACKAGES ***
%
\usepackage{array}
% Frank Mittelbach's and David Carlisle's array.sty patches and improves
% the standard LaTeX2e array and tabular environments to provide better
% appearance and additional user controls. As the default LaTeX2e table
% generation code is lacking to the point of almost being broken with
% respect to the quality of the end results, all users are strongly
% advised to use an enhanced (at the very least that provided by array.sty)
% set of table tools. array.sty is already installed on most systems. The
% latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/array


% IEEEtran contains the IEEEeqnarray family of commands that can be used to
% generate multiline equations as well as matrices, tables, etc., of high
% quality.




% *** SUBFIGURE PACKAGES ***
\ifCLASSOPTIONcompsoc
  \usepackage[caption=false,font=normalsize,labelfont=sf,textfont=sf]{subfig}
\else
  \usepackage[caption=false,font=footnotesize]{subfig}
\fi
% subfig.sty, written by Steven Douglas Cochran, is the modern replacement
% for subfigure.sty, the latter of which is no longer maintained and is
% incompatible with some LaTeX packages including fixltx2e. However,
% subfig.sty requires and automatically loads Axel Sommerfeldt's caption.sty
% which will override IEEEtran.cls' handling of captions and this will result
% in non-IEEE style figure/table captions. To prevent this problem, be sure
% and invoke subfig.sty's "caption=false" package option (available since
% subfig.sty version 1.3, 2005/06/28) as this is will preserve IEEEtran.cls
% handling of captions.
% Note that the Computer Society format requires a larger sans serif font
% than the serif footnote size font used in traditional IEEE formatting
% and thus the need to invoke different subfig.sty package options depending
% on whether compsoc mode has been enabled.
%
% The latest version and documentation of subfig.sty can be obtained at:
% http://www.ctan.org/pkg/subfig


  \usepackage{color}

% *** FLOAT PACKAGES ***
%
%\usepackage{fixltx2e}
% fixltx2e, the successor to the earlier fix2col.sty, was written by
% Frank Mittelbach and David Carlisle. This package corrects a few problems
% in the LaTeX2e kernel, the most notable of which is that in current
% LaTeX2e releases, the ordering of single and double column floats is not
% guaranteed to be preserved. Thus, an unpatched LaTeX2e can allow a
% single column figure to be placed prior to an earlier double column
% figure.
% Be aware that LaTeX2e kernels dated 2015 and later have fixltx2e.sty's
% corrections already built into the system in which case a warning will
% be issued if an attempt is made to load fixltx2e.sty as it is no longer
% needed.
% The latest version and documentation can be found at:
% http://www.ctan.org/pkg/fixltx2e


%\usepackage{stfloats}
% stfloats.sty was written by Sigitas Tolusis. This package gives LaTeX2e
% the ability to do double column floats at the bottom of the page as well
% as the top. (e.g., "\begin{figure*}[!b]" is not normally possible in
% LaTeX2e). It also provides a command:
%\fnbelowfloat
% to enable the placement of footnotes below bottom floats (the standard
% LaTeX2e kernel puts them above bottom floats). This is an invasive package
% which rewrites many portions of the LaTeX2e float routines. It may not work
% with other packages that modify the LaTeX2e float routines. The latest
% version and documentation can be obtained at:
% http://www.ctan.org/pkg/stfloats
% Do not use the stfloats baselinefloat ability as the IEEE does not allow
% \baselineskip to stretch. Authors submitting work to the IEEE should note
% that the IEEE rarely uses double column equations and that authors should try
% to avoid such use. Do not be tempted to use the cuted.sty or midfloat.sty
% packages (also by Sigitas Tolusis) as the IEEE does not format its papers in
% such ways.
% Do not attempt to use stfloats with fixltx2e as they are incompatible.
% Instead, use Morten Hogholm'a dblfloatfix which combines the features
% of both fixltx2e and stfloats:
%
% \usepackage{dblfloatfix}
% The latest version can be found at:
% http://www.ctan.org/pkg/dblfloatfix




% *** PDF, URL AND HYPERLINK PACKAGES ***
%
\usepackage{url}
% url.sty was written by Donald Arseneau. It provides better support for
% handling and breaking URLs. url.sty is already installed on most LaTeX
% systems. The latest version and documentation can be obtained at:
% http://www.ctan.org/pkg/url
% Basically, \url{my_url_here}.


\renewcommand\floatpagefraction{.9}
\renewcommand\topfraction{.9}
\renewcommand\bottomfraction{.9}
\renewcommand\textfraction{.1}
\setcounter{totalnumber}{50}
\setcounter{topnumber}{50}
\setcounter{bottomnumber}{50}

\setlength{\floatsep} {3pt plus 1pt minus 1pt}
\setlength{\textfloatsep} {3pt plus 1pt minus 1pt}

\renewcommand{\baselinestretch}{1.0}

% *** Do not adjust lengths that control margins, column widths, etc. ***
% *** Do not use packages that alter fonts (such as pslatex).         ***
% There should be no need to do such things with IEEEtran.cls V1.6 and later.
% (Unless specifically asked to do so by the journal or conference you plan
% to submit to, of course. )


% correct bad hyphenation here
\hyphenation{op-tical net-works semi-conduc-tor}


\begin{document}
%
% paper title
% Titles are generally capitalized except for words such as a, an, and, as,
% at, but, by, for, in, nor, of, on, or, the, to and up, which are usually
% not capitalized unless they are the first or last word of the title.
% Linebreaks \\ can be used within to get better formatting as desired.
% Do not put math or special symbols in the title.
\title{Voronoi-Voting for Robust Passive Locating}


% author names and affiliations
% use a multiple column layout for up to three different
% affiliations
%\author{\IEEEauthorblockN{Michael Shell}
%\IEEEauthorblockA{School of Electrical and\\Computer Engineering\\
%Georgia Institute of Technology\\
%Atlanta, Georgia 30332--0250\\
%Email: http://www.michaelshell.org/contact.html}
%\and
%\IEEEauthorblockN{Homer Simpson}
%\IEEEauthorblockA{Twentieth Century Fox\\
%Springfield, USA\\
%Email: homer@thesimpsons.com}
%\and
%\IEEEauthorblockN{James Kirk\\ and Montgomery Scott}
%\IEEEauthorblockA{Starfleet Academy\\
%San Francisco, California 96678--2391\\
%Telephone: (800) 555--1212\\
%Fax: (888) 555--1212}}

% conference papers do not typically use \thanks and this command
% is locked out in conference mode. If really needed, such as for
% the acknowledgment of grants, issue a \IEEEoverridecommandlockouts
% after \documentclass

% for over three affiliations, or if they all won't fit within the width
% of the page, use this alternative format:
%
%\author{\IEEEauthorblockN{Michael Shell\IEEEauthorrefmark{1},
%Homer Simpson\IEEEauthorrefmark{2},
%James Kirk\IEEEauthorrefmark{3},
%Montgomery Scott\IEEEauthorrefmark{3} and
%Eldon Tyrell\IEEEauthorrefmark{4}}
%\IEEEauthorblockA{\IEEEauthorrefmark{1}School of Electrical and Computer Engineering\\
%Georgia Institute of Technology,
%Atlanta, Georgia 30332--0250\\ Email: see http://www.michaelshell.org/contact.html}
%\IEEEauthorblockA{\IEEEauthorrefmark{2}Twentieth Century Fox, Springfield, USA\\
%Email: homer@thesimpsons.com}
%\IEEEauthorblockA{\IEEEauthorrefmark{3}Starfleet Academy, San Francisco, California 96678-2391\\
%Telephone: (800) 555--1212, Fax: (888) 555--1212}
%\IEEEauthorblockA{\IEEEauthorrefmark{4}Tyrell Inc., 123 Replicant Street, Los Angeles, California 90210--4321}}




% use for special paper notices
%\IEEEspecialpapernotice{(Invited Paper)}




% make the title area
\maketitle

% As a general rule, do not put math, special symbols or citations
% in the abstract
\begin{abstract}
Passive locating by capturing mobile phone's WiFi probing messages suffers inaccuracy and not robust problem, especially in zero-calibrated environments. The main reason is because of the inaccuracy of RSS-ranging; the measurement noises;  and the dynamic effects due to the environment and the phone status.  
This paper investigates whether the ordinal relationships  among the radio signal strengths (RSS),  measured by different Access Points (APs) from a common phone can help to improve the phone's locating accuracy. The trustworthy ordinal relationships (TOR) among the captured RSSs at different APs are extracted. Each TOR generates a partition of the space to narrow down the possible location of the phone, i.e., locating the phone by a voronoi cell.  But the number of TORs is general limited at a time instance, resulting at rather large voronoi cell,  i.e., large uncertainty of the phone's location.  Successive TORs   produces  voronoi cells of different shapes, because of the dynamic noise impacts at different time.  Fortunately, each of these voronoi cells is a polygon. A polygon clipping-based voting method is proposed  to generate confidential phone location by the most intersected convex hull (MICH). It helps to improve the phone locating accuracy overtime. However, as the phone moves, the key to use MICH  is to prevent it  from being too large nor being vanished. A kernel-based method is proposed for MICH  fusion overtime for tracking the mobile targets. Since MICH provides convex constraints to the target location, a constrained non-linear optimization model is further proposed to calculate the target location by weighted KNN while restricting the convex constraints. We show these methods can improve the locating robustness and accuracy remarkably for passive locating,  which are verified by both simulations and practical experiments. 

%The algorithm, system development, and the performance evaluation results are presented, which show the much improvement of the reliability and accuracy than the state-of-the-art of other zero-calibration algorithms. It provides in average about 1 meters locating error in non-calibrated, dynamic environments and it eliminates almost all extremely hard cases in passive locating.
\end{abstract}

% no keywords




% For peer review papers, you can put extra information on the cover
% page as needed:
% \ifCLASSOPTIONpeerreview
% \begin{center} \bfseries EDICS Category: 3-BBND \end{center}
% \fi
%
% For peerreview papers, this IEEEtran command inserts a page break and
% creates the second title. It will be ignored for other modes.
\IEEEpeerreviewmaketitle



\section{Introduction}
Because the mobile phone is almost a must-have device by all people, and the wide prevalence of WiFi Access Points (APs) in public and office areas,  
investigations of passive person locating by capturing  WiFi probing messages from the smart phones has attracted great attentions.  Such passive locating method doesn't request 
any special APP to be installed on the phone, nor user cooperation, while keeping user nonintrusive. It has great value in many applications, such as customer flow analysis; 
crowd security monitoring; passenger interest mining etc \cite{Smith1991Passive}\cite{Zan2015A}. The working flow of passive locating is that, the mobile phones repetitively 
broadcast WiFi probing messages for either WiFi scanning or connection maintenance, only if its WiFi is not turned off.  When APs collect and transmit these probing  information to  the back-end server, the locations of the phones can be inferred by localization algorithms, such as trilateration based on the received signal strength (RSS). 



However, the main challenges for passive locating are the inaccuracy and not robust problems, mainly because the highly dynamic application scenarios. In passive locating, the mobile phones maybe in pocket, in bag, or in hand. The inner state of the phone maybe working, sleeping or power saving. Users may take phones of a large category of different brands, and phones of different brands my have different probing patterns.  The locating process is also impacted by the environment dynamics. These factors all impact the signal measurements, therefore, leading to highly inaccuracy of the localization results. 


A major approach to deal with the environment impacts  is to train radio-map offline, and to conduct online locating by radio-map matching  \cite{Kushki2005Radio}\cite{yang2015adamap}. 
However,  the application environments in passive locating are generally very large and the application scenarios are  highly dynamic, such as in shopping mall, airport, even in campus or city scale. The laborious training efforts can hardly be paid,  therefore, passive locating in zero-calibrated environment is extremely important for the sense of practical implementation.

In zero-calibrated passive locating, one major approach for locating accuracy and robustness is to learn a suitable RSS-distance model in the specific environment \cite{Yang2015A}\cite{Mahfouz2016Non}, which was approached by either offline parameter learning or  online model regression\cite{Lo2012Adaptive}\cite{yang2015adamap}.  However, the RSS-distance model is generally simple, characterized by several parameters, which can hardly cover the signal noises and environment dynamics. Another major way is to detect and exclude RSS outliers in the location calculation by either majority voting\cite{Ruta2005Classifier} or residue-based voting \cite{Schaffer1990Residue}. But in passive locating,  the number of captured RSSs at a time instance (a snapshot) are generally very limited. This causes difficulty for outlier voting.  Further, the location estimation generally adopts an optimization model\cite{keylist}.  Under the condition of small and rough observation set, the optimization is unreliable and less noise-tolerant.
Therefore, seeking locating accuracy and robustness remains a challenging problem for passive locating, especially in zero-calibrated environments.  


To address these chanllenges, we exploit the  ordinal relationships among the RSS data for improving the location robustness and accuracy. 
The orders among data generally depend less on the accurate values, which tends to be robust if noises are positively correlated. 
In passive locating systems, the noises of measured RSSs  captured from a mobile phone are highly correlated because they are affected by the same environment and the same phone state information. Therefore, methods are proposed to extract \emph{trustworthy ordinal relationships (TOR)}  which requires the difference of RSS values be larger than a threshold. 
Such ordinal relationship is robust to noise. Each TOR narrows down the target location to a half plane,  and multiple TORs define a convex polygon, representing the \emph{feasible region} of the target. But since the number of RSSs are limited in a snapshot, the polygon defined by TORs of one time instance is generally quite large. The location of the phone is highly uncertain. The convex polygons of successive slots maybe different due to the random noises and environment impacts. Fusion of these polygons by polygon clipping can help to vote the 
most intersected convex hull (MICH), representing the most confidential target location despiting the random noises. It helps to improve the locating accuracy overtime.  
  
But when the target is mobile, we devised the key for utilizing the ordinal constraints is to prevent the MICH from being too large nor being vanished.  The desired case is to maintain a MICH around the target, which only exclude the unreasonable noises. Too large feasible region is meaningless in enhancing the location accuracy, while too small region may provide false constraints to  the target's location.  
%Therefore, a series of methods is investigated for enabling a smoothing feasible region overtime based on the successively collected TORs.
%1) Narrowing down the feasible region by thresholding TORs in one snapshot (OS); 2) Selecting the direct intersection area of feasible regions of multiple successive snapshots by polygon clipping (IM). %is directly regarded as target feasible region. %3) Smoothed mergence algorithms considering target movement are adopted to merge feasible regions of successive time.
%Fusion of feasible regions of successive snapshots are modeled as a polygon clipping problem.
%3) A smoothing strategy considering feasible region expansion according to target movement, and 
A kernel-based method is proposed to insure smoothed MICH region to track the target. Further,  by applying the linear  constraints characterizing the MICH as constraints in location estimation, a constrained nonlinear optimization model is proposed to enhance the optimization paradigm.  The effectiveness of these methods is verified by extensive simulations and practical experiments.  We conducted passive locating experiments in an office environment for more than half a year. Among all compared algorithms, the smoothed ordinal constraints outperformed  other algorithms in both location accuracy and location robustness.   Analytical results of RSS patterns  also   verify the  effectiveness of the proposed approaches in different noise conditions. %Extensive  simulations are also conducted to further verified the effectiveness of the smoothed ordinal constraint method in various network and noise settings.  The practical results showed that the smooth ordinal constraint is a promising way to regularize the RSS noises to improve the accuracy and robustness of passive locating.

\section{Problem Model and Preliminaries}
\label{sec: problem model and preliminaries}
In this section, we introduce the mathematical model and notations of passive indoor location. Some fundamental methods in passive location are reviewed and their limitations are discussed.

\subsection{Model and Notations}
Suppose the area-of-interest in which a user is moving is a bounded area $\mathbf{M}$. A mobile phone taken by the user broadcasts probing signal periodically. In the area, there are $N$ probe devices. When the probing signal from the phone is captured by a probing device, the device stores the RSS and MAC address of the phone, and a time stamp. See Figure \ref{figure of background} for illustration of the system of passive locating. Denote the RSS captured by probe $i$ at time $t$ by $S_i^t$ and the position of probe $i$ by $X_i$. The position of user at time $t$ is denoted by $Y^t$. The ultimate task of passive indoor location is to estimate $Y^t$ by $X_i$ and $S_i^{\tau}$ by all measurements collected from $1$ to $t$.
\begin{equation}
\widehat{Y^t} = F(X_i, S_i^\tau : 1 \leq i \leq N, 1 \leq \tau \leq t)
\end{equation}
where $\widehat{Y^t}$ is the estimation of $Y^t$.

\begin{figure}[!t]
\centering
\includegraphics[width=2.5in]{background.pdf}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
\caption{System of passive indoor location}
\label{figure of background}
\end{figure}

%\begin{table}[!t]
%%% increase table row spacing, adjust to taste
%\renewcommand{\arraystretch}{1.3}
%% if using array.sty, it might be a good idea to tweak the value of
%% \extrarowheight as needed to properly center the text within the cells
%\caption{Some important notations}
%\label{table of notations}
%\centering
%%% Some packages, such as MDW tools, offer better commands for making tables
%%% than the plain LaTeX2e tabular which is used here.
%\begin{tabular}{|c|c|}
%\hline
%$\mathbf{M}$ & movement space of user \\
%\hline
%$N$ & number of probes \\
%\hline
%$X_i$ & position of probe $i$ \\
%\hline
%$S_i^t$ & RSS of probe $i$ at time $t$ \\
%\hline
%$Y^t$ & position of user at time $t$ \\
%\hline
%$d_i^t$ & distance between user and probe $i$ at time $t$ \\
%\hline
%$R_t$ & reliable bound of the location of user at time $t$ \\
%\hline
%\end{tabular}
%\end{table}
\subsection{Settings of Passive Locating}
The passive locating problem in practice generally have following setting:
\begin{itemize}
\item No offline radio-map training, since training is time consuming and labor intensive.
\item Number of probing devices are limited, i.e., $N$ is small, which is a general case in practice.
\item High probability of RSS signal loss (a large proportion of $S_i^\tau$ cannot be detected) and the RSS noises are loud.
\end{itemize}
\subsection{Key Problems}
The measured RSS value is generally translated into distance for location calculation, which is mainly based on the free-space signal propagation model \cite{Qiu2013A}:
 \begin{equation}
\textrm{RSS} = \textrm{RSS}_0 - 10 * n_0 * \log_{10} d + e
 \end{equation}
where $\textrm{RSS}_0$ and $n_0$ are two parameters  related to transmission media \cite{Qiu2013A}. $e$ is the measurement noise. As we mentioned above, the noise comes from the impacts of the environment, the electromagnetic interference, spacial shading, the phone internal states and phone placement status. The pattern of RSS noises has great impacts on the location problem. 

We conducted practical experiments in an office environment to investigate the RSS patterns. The results are summarized in Table \ref{table of correlation} and Figure \ref{correlation of RSS}.  It can be concluded that $e$ is highly positive correlated among RSS of all probes. This is reasonable since when mobile phone condition changes, RSS of different probes tends to have the same shifting direction.  A way to make use of the positive correlation of RSS of different probes is to consider the ordinal relations of RSS, which will be detailed in the next section.

\subsection{Discussion of fundamental algorithms}
Some methods are generally used for passive location, but they encounter different problems when RSSs are highly noisy and have high loss probability.
\subsubsection{Weighted $k$-nearest neighbor} Weighted $k$-nearest neighbor (KNN) method \cite{Yigit2014ABC} is an efficient way to locate user's position by finding the weighted centroid of $k$ probing devices. %Generally $k$ probes with highest RSS are picked and the weighted center of the $k$ probes is estimated as the user location. %Because the number of probes are small, different weights can be assigned to probes and the location can be estimated by taking a convex combination of $k$ nearest probes.
%Suppose probe $1$ to $k$ are the $k$ closest probes to the mobile phone, we can get approximated distance $\widehat{d_i^t}$ between probe $i$ and the user at time $t$ by
%\begin{equation}
% \widehat{d_i^t} = 10^{\frac{1}{10 * n_0}(\textrm{RSS}_0 - S_i^t)}
%\end{equation}
%
%Take $w_i^t = 1/\widehat{d_i^t}^2$ \cite{} as the weight of probes $i$ at time $t$, then the location estimation of $Y^t$ is
%\begin{equation}
%\widehat{Y^t} = \frac{\sum_{i=1}^k w_i^tX_i}{\sum_{i=1}^k w_i}
%\end{equation}
Although weighted KNN method is less affected by correlated noises of RSS when the condition of mobile phone changes, it is highly impacted by the number and the  topology of probes.  When the density of probes is low, weighted KNN can only make a coarse estimation. In addition, it always locate the user into the convex hull of the probes. When user is actually outside the convex hull of the probes, it cannot give a correct location.  %Figure \ref{knn} gives an example, when the user is outside the convex hull of the probes, but is estimated as inside by weighted KNN. % of incorrect location due to unsuitable topology of probes.

%\begin{figure}[!t]
%\centering
%\includegraphics[width=2.5in]{knn.pdf}
%% where an .eps filename suffix will be assumed under latex,
%% and a .pdf suffix will be assumed for pdflatex; or what has been declared
%% via \DeclareGraphicsExtensions.
%\caption{An example of incorrect location for k-nearest neighbor method}
%\label{knn}
%\end{figure}

\subsubsection{Least square method} Least square method \cite{Helmke1995Critical} is another widely used method for passive locating. A set of linear equations about the location of user can be derived from observations and empirical function. Then by least square method,  an estimation of location can be obtained.

% For every pair of probes $i$ and $j$, we have
%$(Y^t - X_i)^2 = (d_i^t)^2$ and $(Y^t - X_j)^2 = (d_j^t)^2$. By taking a difference we have
%$$2(X_j - X_i)Y^t = (d_i^t)^2 - (d_j^t)^2 + X_j^2 - X_i^2$$
%which is a linear relation about $Y_i^t$. %Fixing probe 1 and taking difference on probe 1 for all other probes we have a set of linear relation
%$$\{2(X_j - X_1)Y^t = (d_1^t)^2 - (d_j^t)^2 + X_j^2 - X_1^2 \mid 2 \leq j \leq N\}$$
%Replace all $d_i^t$ by estimated $\widehat{d_i^t}$ from empirical function and by least square method $Y^t$ can be estimated from this linear system.
%A set of linear equations can be obtained using the same way and $Y^t$ can then be calculated by solving the linear equation using least square method.
The limitations of least square method is that: 1) it depends on empirical RSS-distance model, which is unreliable; 2) It is sensitive to the topology of the probes. Ill-conditioned observation topology may lead to huge location error.

\subsubsection{Optimization method} Some optimization schemes have been applied in passive location as well. For example, by assuming observation noises are zero-mean, %the logistic likelihood function of target location at time $t$ can be written as:
%$$ L = - \sum_{i=1}^N(S_i^t - \textrm{RSS}_0 + 10* n_0 * \log_{10} \lVert Y^t - X_i \rVert)^2 $$
The location of the user can be estimated  by maximizing the likelihood function \cite{Xiaojie2011Detector}. However, the  weakness of the optimization methods is that the empirical function is unreliable, and the optimization method generally ignores the correlation of noises. %The mobile phone suffers frequently condition changes,  so the shifts of RSS is common. Gaussian noise distribution assumption is too simplified to cause prediction drift away from the ground truth.

So above basic methods in passive location generally encounter problems due to high and correlated noises of RSS measurements. %The RSS data should be carefully processed because of its small number and large noises. %In addition, to get a more effective way to estimate location of the user, the RSS influence of $E_0$ and $E_1$ should be investigated comprehensively and filtered in a suitable way.
Methods to deal with the RSS noises for robust passive location are critically required.

\section{Order-based Passive Locating}
In this section, we firstly introduce the overview of  proposed system and methodologies for passive locating, and then focus on the ordinal-base methods to deal with noises and environment impacts.
\subsection{System Overview}
The problems  to be addressed in passive locating  include: 1) RSS signal loss problem, which causes the RSS measurements obtained in each snapshot are limited,  and the measurements are intermittent in successive snapshots; 2) the empirical RSS-distance function is not accurate; 3) the magnitude of RSS noise is comparable to the RSS values.

To address above challenges,  we present the  following approaches for passive indoor location:
\begin{enumerate}
\item Collaborative filter (CF) based RSS data preprocessing to deal with data loss and to smooth the measurement noises
\item Trustworthy Ordinal Relationship (TOR) extraction to bound the feasible region of the user, and feasible region smoothing method as the target is moving
\item A constrained nonlinear optimization model to calculate the location of user by the smoothed ordinal constraints
\end{enumerate}

We will briefly introduce the collaborative filter method, whose details can be referred to \cite{Ye2016}\cite{Su2009A} for dealing with RSS noises and RSS loss. This paper will focus on the extraction and the fusion of ordinal relationships.
\begin{figure*}[!t]
\centering
\subfloat[Feasible region generation by TOR in one snapshot]{\includegraphics[width=2.5in]{overview1.pdf}%
\label{mean}}
\hfil
\subfloat[Mergence of feasible region in successive snapshots]{\includegraphics[width=2.5in]{overview2.pdf}%
\label{var}}
\caption{Overview of constrained passive location}
\label{overview}
\end{figure*}

\subsection{Collaborative Filter based Data Preprocessing}
For locating one target, the RSS measurements from 1 to $t$, captured at the $N$ probing devices  form a matrix of $N$ rows and $t$ columns. Due to the RSS loss and the measurement noises, many entries of the matrix are missing and the existing entries are noisy.
The goal of data preprocessing is to fill the missing entries and to smooth the existing entries.

The data preprocessing consists of two steps.  1)  Predict unknown RSS data based on correlation of known data; 2) Smooth the filled RSS data by polynomial fitting over time. Collaborative filter (CF) \cite{Schafer2007Collaborative} was exploited to make predictions for unknown RSS data, which considers both data correlation over time and across probing devices. %The data correlation has been proved in Table \ref{table of correlation} and Figure \ref{correlation of RSS}.

In proposed CF method, two predictions are made separately by polynomial fitting over time and weighted interpolation across probing devices. If the difference of two predictions is smaller than a threshold, the missing value will be filled by their average value. CF recursively executes above operations for a fixed number of times. After filling empty values, RSS data are smoothed by polynomial fitting over time, to reduce the impacts of RSS noises \cite{Lanza2010Robust}.

\subsection{Exploit the Robust Ordinal Relationships}
For two RSS measurements $S_i^t$ and $S_j^t$,  without loss of generality, if $S_i^t - S_j^t \ge T_h$, we call there is a trustworthy ordinal relationship (TOR) between $S_i^t$ and $S_j^t$, in which $T_h$ is a noisy threshold.  TOR is generally robust to measurement noises and the phone state changes because: 1)  the RSS noises are  positive correlated among all probes; 2) due to inaccurate empirical function from RSS to distance, the ordinal relation is more reliable than the values of RSS.

Practically, at time $t$, an ordinal relation can give a reliable constraint to the location of user. Suppose at time $t$, $S_i^t \geq S_j^t$, this indicates $(X_i - Y^t)^2 \leq (X_j - Y^t)^2$. Then
$$ 2(X_j - X_i)Y^t \leq X_j^2 - X_i^2 $$
This is a linear constraint of $Y^t$ representing a half space cut on the feasible region of $Y^t$. This kind of cut is named as \emph{ordinal cut (OC)}. %since it is induced by an ordinal relation between a pair of probes.
Multiple OCs will characterize a polygon, which is the feasible region characterized by TORs among the probes. This region is trustworthy since the TORs are robust to noise and phone states.


\subsection{OC mergence}
Therefore, to improve location robustness against noise in passive location, the ordinal constraints are exploited. Figure \ref{overview} illustrates the basic idea of utilizing the ordinal constraints to enhance the robustness and accuracy of passive locating.

Figure \ref{overview}a shows how the TORs can characterize a feasible region in one snapshot. Each trustworthy ordinal relationship characterize an ordinal cut, and multiple ordinal cuts define the feasible region.  Figure\ref{overview}b illustrates how the feasible regions obtained in successive snapshots can be merged to narrow down the feasible region of the target and improve the location accuracy. The feasible region in each time slot is a polygon, and polygon clipping is applied to merge the feasible regions of multiple snapshots.

But, because the large noises of RSS and the limited number of probing devices, some key problems can be seen for utilizing the ordinal constraints.
\begin{itemize}
\item Limited number of probing devices, and the selection of confident $T_h$ may cause the feasible region (denoted by $R_t$) be large. When the feasible region is large, it loses the capability to narrow down the feasible region of the target.
\item When the target is moving, and due to the measurement noises,  merged $R_t$ of the successive snapshots be separated or be very small. Such scenario should be avoided, because $R_t$ is likely to provide wrong restrictions to the target location.
%\item The location algorithm should be revised to integrate with the constraints.
\end{itemize}
Therefore, to exploit the TORs to enhance the accuracy of passive locating, $R_t$ should give smoothed constraints overtime. We desire a reasonable feasible region around target which only exclude the confidentially infeasible regions.  %To deal with these requirements,  we investigate a series of methods for smoothed feasible region mergence overtime .

\subsection{Constrained nonlinear optimization}
\label{constrained nonlinear programming}
The estimation of $Y^t$ based on $R_t$ is treated by solving a constrained nonlinear programming problem. Having smoothed RSS and empirical function $F$, $Y^t$ can be optimized, by solving an optimization problem to minimize the sum of square error, while satisfying the constraints derived by ordinal constraints, i.e.,  $R_t$.

%There are several strategies to solve this problem.  For example, some simple learning algorithm such as k-nearest neighbor search or least square method can obtain an estimation of user's position. However, the classical version of these algorithm can not accommodate constraints. Also, the precision of the empirical formula plays an important role in the correctness of estimation but empirical formula fails for many situations. It is a pressing need to add reliable OCs to enhance the robustness of the optimization.
More specifically, The following constraint programming problem will be optimized:
\begin{align*}
&\textrm{Minimize}_{x} \sum_{i, j} \left(\frac{F(\lVert Y^t - X_i \rVert_2) - S_i^t}{S_i^t}\right)^2 \\
& \textrm{Subject to } x \in R_t \cap \mathbf{M}
\end{align*}
This programming can be handled by many standard optimization tools such as interior point method \cite{Byrd2000A}\cite{Waltz2006An} or active set \cite{Fletcher1963A}\cite{Goldfarb1970A}.

Some modifications can be made on such optimization. For example $\textrm{RSS}_0$ and $n_0$ in empirical function can be taken as optimization variables and weights can be added on the sum of square differences. Besides we can remove the constraints by adding a penalty to objective.

\section{Smoothed Ordinal Constraints for Passive Location}
How to utilize the ordinal cuts smoothly to improve the location accuracy and robustness are focused in this section.

\subsection{Narrow Down the Feasible Region}
\label{os}
Note that to select the robust ordinal relationships against noises. %, only the trustworthy ordinal relationships are selected. It requires the difference between RSS values to be larger than a threshold $T_h$. Such trustworthy ordinal relationship forms an ordinal cut (OC). The target lies on one side of this cut.
The setting of this threshold can help to overcome the ordinal relationship to be   reversed. The cut reversal means $S_i^t > S_j^t$ but in fact $(X_i - Y^t)^2 > (X_j - Y^t)^2$ for some probes $i$ and $j$, which means the target is predicted to the wrong side of the cut.

So selection of  $T_h$  falls into the dilemma of reliability and accuracy. When  $T_h$ is large, that OCs are confident, but the region of $R_t$ maybe too large to effectively assist  future optimization. When $T_h$  is small, the region of $R_t$ is small, but becomes not reliable. Sometimes the noise can be larger than $T_h$, which leads to reversed cuts.

In this paper, confident, large $R_t$ is preferred, because it can further  be online narrowed down by  OCs of successive snapshots.  $R_t$  is indicating the possible region of the target for the constrained optimization problem (in Section \ref{constrained nonlinear programming}). According to high noises, $R_t$ cannot be too small. Otherwise, $R_t$ will be too restricted and there is high risk that the correct location is not in  $R_t$ and the optimization may give incorrect result.

\begin{algorithm}
\caption{Trustworthy Ordinal Cut}
\begin{algorithmic}
\REQUIRE $S_i^t$: RSS from probe $i$ at time $t$, $(x_i, y_i)$: position of probe $i$
\ENSURE $R_t = \{x \mid A_t x \leq b_t\}$: reliable region at time $t$ by slack ordinal cut
%\STATE Hello
\FOR{$(i, j)$ pair of probe}
\IF{$|S_i^t - S_j^t| > T_h$}
\IF{$S_i^t > S_j^t$}
\STATE add $2(x_j - x_i)x + 2(y_j - y_i)y \leq x_j^2 + y_j^2 - x_i^2 - y_i^2$ into $A_tx \leq b_t$
\ELSE
\STATE add $2(x_j - x_i)x + 2(y_j - y_i)y \geq x_j^2 + y_j^2 - x_i^2 - y_i^2$ into $A_tx \leq b_t$
\ENDIF
\ENDIF
\ENDFOR
\STATE $R_t = \{x \mid A_t x \leq b_t\}$
\end{algorithmic}
\end{algorithm}
%\IF{$Y_i^t > Y_j^t$}
%add $2(x_j - x_i)x + 2(y_j - y_i)y \leq x_j^2 + y_j^2 - x_i^2 - y_i^2$ into $A_tx \leq b_t$
%\ENDIF
\subsection{Smoothed Mergence of  OCs in Successive Slots}
%Sometimes a good $\Lambda$ can not always give a non-empty $R_t$ and often $R_t$ is large as some OCs are removed.
\subsubsection{Direct Polygon Clipping}
\label{im}
So during mergence of $R_t$, we should avoid the case when $R_t$ is too small, which can hardly merge with later OCs.  Note that the direct intersection area of $R_t$ of successive snapshots  gives the feasible region satisfying the most number of successive OCs. Since each reliable region is a polygon, direct mergence of OCs of successive snapshots can be modeled as a polygon clipping problem. However, due to noises, when there are successive snapshots in which the feasible regions don't have overlapped region,  $R_t$ will be separated into multiple components, as shown in Figure \ref{intersection}.
In this case $R_t$ can not be expressed by linear constraints and we can hardly tell which component the target maybe locate in.


%In addition, the time continuity of user's movements can also be utilized to generate constraints of the target to further refine the intersection region over time (IROT).
%The  OCs  in a time window $T$ are considered. %and the maximum intersection of all these OCs can be $R_t$ to estimate average position during this time window $T$.
%IROT makes use of time to smooth the occasional reversed cut. See Figure \ref{max intersection} for the illustration of MIR and MIROT. The left most graph shows MIR for time $t$ and the number on the region indicates the number of OCs being satisfied. The right two graphs shows the maximum intersection over time which reduce and size of $R_t$. In general $R_t$ is confined to a small size for maximum intersection over time. However, it is still often the case that $R_t$ can not continuous change over time and high computation load to find MIR and MIROT undermines its practical application.

\begin{figure}[t]
\centering
\includegraphics[width=3.5in]{intersect.pdf}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
\caption{(a) finding intersections by polygon clipping, which may lead to separated regions. (b) finding intersections by expanding the feasible region to consider the target movement}
\label{intersection}
\end{figure}


\subsubsection{Expand $R_t$ by Considering Target Movement}
To smooth OC mergence in successive snapshots, the continuity of user's movement can be utilized. And  it can be seen  the user movement can be very easily integrated into the feasible region mergence.

Let $\{x \mid Ax \leq b\}$ denote the intersection of several OCs. Each row of $A$ should be normalized to a unit vector and each element of $b$ should be scaled accordingly for the simplicity of further exposition. We can generate $R_{t+1}$ from previous $R_t$ easily by considering user movement.  Suppose $R_t = \{x \mid A_tx \leq b_t \}$ is a reliable region at time $t$. At time $t+1$, the user may move,  so $R_t$ should be enlarged to accommodate the user's movements. Take $\Delta$ to be the upper bound of user's moving distance from time $t$ and $t + 1$, then the \emph{expansion} of $R_t$ to $R_t'$ can be modeled as
\begin{equation}
R_t' = \{x \mid A_tx \leq b_t + \Delta\}
\end{equation}
which includes all possible user's position caused by possible movements. But it can be seen from Figure \ref{intersection}b, even if $R_t$ is expanded by user movement, the noises may still cause the intersection area very small, which makes $R_t$ over restricted, which is hard to merge with later constraints and have high risks of losing the target.
\subsubsection{Smoothed Mergence by Considering a Kernel}
Therefore, an intuition is that the constraint in time $t + 1$ should not cut down a too large proportion of $R_t'$. Otherwise $R_{t+1}$ will be small and increases the risk of losing the target.

If we think $R_t$ is reliable, then $R_t' = \{x \mid A_tx \leq b_t + \Delta\}$ is the expansion of  $R_t$ to consider user movement towards outside of $R_t$. $R_{t+1}$ should always be inside $R_t'$ as user can not move further than $\Delta$. And the \emph{kernel} of $R_t$, which is defined as $R_t'' = \{x \mid A_tx \leq b_t - \Delta\}$ should always be inside $R_{t+1}$ as $R_t''$ is the overlapping area of all possible translations of $R_t$ by distance less than $\Delta$. Extending above observations, we obtain the following rule:
\begin{equation}
 R_t'' \subseteq R_{t+1} \subseteq R_t'
\end{equation}

In this way, we merge the feasible regions of successive snapshots, and can guarantee the feasible region is non-empty and continuously changing over time.

 \subsubsection{Smoothed Mergence by Constriants Modification}
 \label{ek}
 Practically, for one OC $\alpha x \leq \beta$ of time $t+1$, the deepest possible cut into $R'_t$  is $\alpha x \leq \beta^*$ where $\beta^* = \max\{\alpha x \mid A_tx \leq b_t - \Delta\}$. Then $\beta$ should be modified to $\min\{\beta, \beta^*\}$ to avoid violating $R_{t + 1} \supseteq R_t''$. $\beta^*$ can be obtained efficiently by linear programming. The geometric interpretation of this modification is that every cut getting through the kernel should be moved to the border of the kernel with the same direction. In this way the generated region is always non-empty and continuously changing over time. See Figure \ref{expansion and kernel} for demonstration of region expansion and region's kernel.
 


\begin{figure}[!t]
\centering
\includegraphics[width=3.5in]{ek.pdf}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
\caption{expansion and kernel}
\label{expansion and kernel}
\end{figure}


Suppose the feasible region at  $t + 1$ after modification to include the kernel is $Ax \leq b'$, then the reliable region $R_{t+1}$ for  $t+1$ will be:
\begin{equation}
R_{t+1} = \{x \mid R_t' \cap Ax \leq b' \} = \{x \mid A_tx \leq b_t + \Delta \cap Ax \leq b'\}
\end{equation}

In this way the OCs in time $t+1$ are incorporated into previous reliable region and new intersection gives a new reliable region in time $t+1$. Feasible regions of $A_tx \leq b_t + \Delta$ and $Ax \leq b'$ are two polygons geometrically, so $R_{t+1}$ is the overlap of these two polygons and general polygon clipping algorithm \cite{Vatti1992A} can be used to effectively find $R_{t+1}$. The algorithm is given in Algorithm \ref{algorithm2}.  In Figure \ref{constraints}, the second figure shows the kernel and expansion of $R_t$; the third figure shows the modification of OCs;  and the last gives $R_{t+1}$.

%A special case for region smoothing is that the reliable region is small when the number of probes is relatively large. When the reliable region is too small to get a non-empty kernel, a special treatment of the region is to stop cutting the region at current step so the region only expands by one step width on the boundary. Usually this operation can stabilize the reliable region and reduce possible errors.

\begin{algorithm}
\caption{Region smoothing by expansion and kernel}
\begin{algorithmic}
\REQUIRE $R_t = \{x \mid A_tx \leq b_t \}$: reliable region at time $t$,  $Ax \leq b$: ordinal cut in time $t+1$
\ENSURE $R_{t+1} = \{x \mid A_{t+1}x \leq b_{t+1}\}$: reliable region at time $t + 1$
\FOR{$\alpha_t x \leq \beta_t$ constraint in $A_tx \leq b_t$}
\STATE $\beta_t' \to \beta_t + \lVert \alpha_t \rVert_2 \Delta$
\STATE $\beta_t'' \to \beta_t - \lVert \alpha_t \rVert_2 \Delta$
\ENDFOR
\STATE All $\alpha_t x \leq \beta_t'$ comprise $A_t x \leq b_t'$
\STATE All $\alpha_t x \leq \beta_t''$ comprise $A_t x \leq b_t''$
\IF{$A_tx \leq b_t''$ is feasible}
\FOR{$\alpha x \leq \beta$ constraint in $Ax \leq b$}
\STATE $\beta^* = \max\{\alpha x \mid A_tx \leq b_t''\}$
\STATE $\beta' \to \min\{\beta, \beta^*\}$
\ENDFOR
\STATE All $\alpha x \leq \beta'$ comprise $A x \leq b'$
\STATE $R_{t+1} = \{x \mid A_tx \leq b_t' \cap Ax \leq b'\}$
\ELSE
\STATE $R_{t+1} = \{x \mid A_tx \leq b_t'\}$
\ENDIF
\end{algorithmic}
\label{algorithm2}
\end{algorithm}

\begin{figure}[!t]
\centering
\includegraphics[width=3.5in]{constraints.pdf}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
\caption{constraint modification in smoothed mergence}
\label{constraints}
\end{figure}
This method is  devised from practice after investigating different algorithms in almost half-a-year of time. We validate its effectiveness from  theoretical analysis, simulations and also practical experiment results. 

\subsection{Algorithm analysis}
In this section, the feasibility of our algorithm is investigated. Some lower bounds are given by theoretical analyses of constraint smoothing algorithm.
\begin{theorem}
Suppose at time $t$, the minimum distance between user and region $R_t$ satisfies $d(x, R_t) \leq n\Delta$, then at time $t+1$, the minimum distance between user and region $R_{t+1}$ satisfies $d(x, R_{t+1}) \leq (n-1)\Delta$ for large $n$.
\end{theorem}
\begin{proof}
For large $n$, the minimum distance between $R_t = \{x \mid A_tx \leq b_t\}$ and $x$ is large. Then for cuts which cut through $A_tx \leq b_t'$, with high probability the cut can not be reversed by noise. For cut shifted to the boundary of the kernel, the kernel should be on the same side of the cut as $x$. This guarantees that $R_{t+1}$ will approach to $x$. Since $A_t \leq b_t'$ enlarge the boundary by $\Delta$ and further modified cut can not separate $x$ from current region, the minimum distance $d(x, R_{t+1}) \leq (n-1)\Delta$.
\end{proof}
This theorem shows $R_t$ will converge to $Y^t$ and $\Delta$ indicates approaching speed when user and $R_t$ are disjoint.
\begin{theorem}
Suppose at time $t$, the user is inside the kernel of $R_t$, then at time $t+1$, the minimum distance between $R_{t+1}$ and $x$ satisfies $d(R_{t+1}, x) \leq \Delta$
\end{theorem}
\begin{proof}
If user is inside the kernel of $R_t$, by the promise of the algorithm, the kernel must be retained in feasible region of $R_{t+1}$. Since the upper bound of user's moving distance is $\Delta$ in one time unit, the minimum distance $d(x, R_{t+1}) \leq \Delta$.
\end{proof}
This theorem shows the $Y^t$ can not get far away from $R_t$ when they are close.
\begin{theorem}
The $R_t$ can not grows to infinity at any time $t$.
\end{theorem}
\begin{proof}
When the $R_t$ expands to sufficient large size, any constraints will cut through the kernel of current $R_t$. By cut modification in the algorithm, all these cuts should be moved to surround the kernel. For enough probes and OCs, the modified cut will reduce the boundary of the $R_t$ by width $d$ which stops the $R_t$ from growing.
\end{proof}
This theorem guarantees the validity of the $R_t$. In general the size of the $R_t$ is stabilized around a certain size related to the number of probes and intensity of noise.

\begin{figure*}[!t]
\centering
\subfloat[mean locating error as a function of mean value of Gaussian noise]{\includegraphics[width=1.7in]{mean.pdf}%
\label{mean}}
\hfil
\subfloat[mean locating error as a function of standard deviation of Gaussian noise]{\includegraphics[width=1.7in]{var.pdf}%
\label{var}}
\hfil
\subfloat[mean locating error as a function of missing ratio of RSS data]{\includegraphics[width=1.7in]{loss.pdf}%
\label{loss}}
\hfil
\subfloat[mean and max locating error of OC algorithms]{\includegraphics[width=1.7in]{sgenoc.pdf}%
\label{oc}}
\caption{locating error}
\end{figure*}

\section{Simulation Results}
Extensive simulations and practical experiments were carried out to validate the effectiveness of the proposed methods. 
\subsection{Experiment Setup}

  A simulation experiment for passive location is conducted in MATLAB \cite{MATLAB:2015}.
   Since one mobile phone can only be detected by a small number of probes, we simulated  8 probes to track a mobile phone in a map with the size of $1250 \times 710 \textrm{pix}^2$ ($18.75 \times 10.65\textrm{m}^2$).
  %The second reason why the number of generated wifipixes is so low is that in actual passive location, only a small number of wifipixes, usually lower than 10, can capture signal of one phone.
  %And only a small number of probe, usually lower than 10, can capture signal of one phone.
  20 simulated paths are generated randomly and the length of each path is around 350pix-length (5.25m). Each path is divided into 20 uniformly distributed locating points and RSS is calculated by $\textrm{RSS}=\textrm{-RSS}_0 - 10 * n * \log_{10} d$ where $d$ is the distance between each locating point and probe.
  %each of which is divided into 20 uniformly distributed locating points.
 % For each pair of locating point and wifipix, RSS can be calculated by $\textrm{RSS}=\textrm{-RSS}_0 - 10 * n * \log_{10} d$ where $d$ is the distance of the pair.
  %We add biased Gaussian noise to calculated RSS data, the mean value of which denoting the drifting of RSS $E_1$ and unbiased Gaussian component denoting $E_0$.
  We add drifting of RSS and unbiased Gaussian noise to RSS data.
  As a large proportion of RSS data cannot be detected in practical passive locating system, we simulate the RSS data loss by random missing of the RSS data. 
  
  For comparison, three zero calibration locating approaches, 1) max likelihood, 3) least square and 3) weighted KNN are implemented to be compared with the proposed method. There  applicable scenarios and limitations have been introduced in Section \ref{sec: problem model and preliminaries}.
%Max likelihood and least square are both mathematical optimization techniques. Their goal is to find the best position by minimizing the square of the error. Max likelihood is to minimize RSS error, while least square is to minimize distance error. Weighted KNN calculate the weighted average position of top-K nearest probe devices.
%The start position of max likelihood is set correctly and initial VOT area is set as the rectangular area with the size of $100 \times 100 \textrm{pix}^2$ centered at correct initial position.

We consider two metrics for performance evaluation, location robustness and locating accuracy. For locating robustness, three influence factors on positioning are concretely analyzed, including signal drifting, standard deviation of unbiased Gaussian noise and the missing ratio of RSS data. To evaluate locating accuracy under different ordinal constraint fusion methods, average location errors by one snapshot (OS) (Section \ref{os}), intersection of multiple snapshots (IM) (Section \ref{im}) and intersection of multiple snapshots with expansion and kernel (EK) (Section \ref{ek}) will be compared comprehensively,  and general locating performance of EK will be compared with the three fundamental algorithms.
%The simulation experiment is organized into 2 categories:
% \begin{enumerate}
% \item Locating robustness. The effect of 3 factors on VOT are concretely analyzed including mean value of Gaussian noise, standard deviation of Gaussian noise and the missing ratio of RSS data.
% \item Locating accuracy. General locating accuracy of VOT are compared with other three state-of-the-art methods.
% \end{enumerate}


\subsection{Robustness VS signal drifting of RSS}
This subsection is to investigate the impact of signal drifting on locating performance.
In order to mitigate the randomness, the missing ratio and standard deviation of Gaussian noise are set as $0.3$ and $5$.
Experiments are conducted by varying signal drifting from $1$ to $10$.
%The effect of the mean value of Gaussian noise is evaluated first.
%The missing ratio and standard deviation of Gaussian noise are set as $0.3$ and $5$.
See Figure \ref{mean} for comparison of the average locating accuracies of EK, max likelihood, least square and weighted KNN.
%A Gaussian noise component with mean value from $1$ to $10$ is added to an unbiased noise, and locating errors are calculated for each of them.
%The average locating error as a function of signal is plotted in Fig...
We can see when signal drifting becomes larger, locating errors of EK and weighted KNN increase slightly, while that of max likelihood and least square increase sharply.
%We can see VOT and weighted KNN are robust to the mean value of Gaussian noise, while max likelihood and least square are not.
Max likelihood and least square works well when signal drifting is small, but works quite poorly even if signal drifting becomes a little larger. The locating errors of EK are generally smaller than the other three locating methods.

\subsection{Robustness VS mean value of Gaussian noise}
The effect of standard deviation of Gaussian noise on locating accuracy is assessed. The missing ratio is set as $0.3$ and RSS drifting is set as $5$. The standard deviation of Gaussian noise is set from 1 to 5 and corresponding locating errors of four methods are calculated. The results are shown in Figure \ref{var}. As we expected, the locating results of all above locating methods become worse when the standard deviation of Gaussian noise becomes larger. EK shows more accurate locating results than the others. It shows EK's good robustness to the standard deviation of Gaussian noise.

\subsection{Robustness VS missing ratio of RSS data}
 The locating robustness to data missing is evaluated in this subsection. RSS drifting and standard deviation of Gaussian noise are both set as $5$. The missing ratio is chosen from $0.1$ to $0.5$. The locating errors of EK, max likelihood, least square and weighted KNN are calculated separately, which are plotted in Figure \ref{loss}. It turns out that all locating methods show stable performance even if missing ratio of RSS data is large, which shows the efficiency of the collaborative filter used to clean data. The general locating error of EK is smaller than other three methods.
%It turns out that VOT is most robust to data missing.

\subsection{Accuracy VS OC methods}
In the subsection, we compare the locating accuracy of OS, IM and EK. The standard deviation of Gaussian noise and the missing ratio of RSS data is set as $5$ and $0.3$. RSS drifting varies randomly between $0$ to $10$ to improve universality of locating results. See Figure \ref{oc} for average locating errors of 3 OC methods. We can see the average locating errors of 3 OC algorithms is similar. The max locating error of EK is smaller than other two OC algorithms, which shows the best robustness.

\subsection{Accuracy VS zero calibration algorithms}
The general locating accuracy of EK and the other three zero calibration algorithms will be evaluated. The standard deviation of Gaussian noise is set as $5$ and the missing ratio of RSS data is set as $0.3$. The RSS is also shifted by a randomly chosen value from $0$ to $10$. Locating errors of four methods are calculated separately and the their comparison results are shown in Figure \ref{accuracy}. We can see the locating error of EK is the smallest. Max likelihood and weighted KNN work the second best, and least square works the worst.

\begin{figure*}[!t]
\centering
\subfloat[CDF of locating error in simulation]{\includegraphics[width=2.0in]{accuracy.pdf}%
\label{accuracy}}
\hfil
\subfloat[CDF of locating error when phone condition changes]{\includegraphics[width=2.0in]{status.pdf}%
\label{CDF status}}
\hfil
\subfloat[CDF of locating error when phone position changes]{\includegraphics[width=2.0in]{position.pdf}%
\label{CDF position}}
\caption{cumulative distribution function}
\end{figure*}

\begin{figure*}[!t]
\centering
\subfloat[mean value of RSS for different type of mobile phone]{\includegraphics[width=2.0in]{mobile_phone_type.pdf}%
\label{type}}
\hfil
\subfloat[mean value of RSS for different inner status of mobile phone]{\includegraphics[width=2.0in]{mobile_phone_status.pdf}%
\label{inner status}}
\hfil
\subfloat[mean value of RSS for different placement of mobile phone]{\includegraphics[width=2.0in]{mobile_phone_position.pdf}%
\label{placement}}
\caption{correlation of RSS}
\label{correlation of RSS}
\end{figure*}

\section{Experiment Result}
\subsection{Experiment Setup}
\emph{1) Implementation:} We choose wifipix \cite{Wifipix}, produced by Beijing Wifipix Company, as probing device to capture RSS data of nearby smartphones in the experiment.
%Wifipix, the probe devices produced by Beijing wifipix company, is able to capture RSS data of nearby smartphones.
Although its scanning period is about 4s, often it can not detect any signal within 1 minute. In addition, sometimes the fluctuation of RSS exceeds 10dbm in the same settings. So RSS data measured by wifipixes are regarded as \emph{weak observations}.
%    Wifipixes are chosen as RSS acquisition equipments in the experiment, which can capture RSS data of nearby % mobile phones. However, due to hardware and cost limit, there is much data missing and noise in collected data.
%Their function is identical to normal router except for their portable size and distinctive RSS measuring characteristics, which means they can capture RSS data of nearby mobile phones and distinguish them with MAC addresses.
%The scanning frequency of wifipixes is also low, about 4 seconds.
%As a result, collected RSS data is regarded as weak observation.
%After data collection, the
Buffered data in wifipixes is transmitted to database Postgres in the Linux server by a node.js program.
When we need to locate one mobile phone in specific time span, corresponding RSS data will be extracted by a java program from Postgres for position calculation.
The snapshot of wifipix and the structure diagram of actual locating system are shown in Figure \ref{wifipix}.

\begin{figure}[!t]
\centering
\includegraphics[width=3.5in]{exp.pdf}
% where an .eps filename suffix will be assumed under latex,
% and a .pdf suffix will be assumed for pdflatex; or what has been declared
% via \DeclareGraphicsExtensions.
\caption{wifipix and system structure}
\label{wifipix}
\end{figure}

\emph{2) Experiment area:} The experiment is conducted in DuShiWangJing 1701, the office environment. It owns the size of 142 square meters. 6 wifipixes are evenly installed in 6 different areas, such as corridors and offices, with 3 meters over the floor for all.
%The heights of wifipixes are approximately equal, so height effect is efficiently eliminated.
%So we just estimate the two dimensional position of the mobile phone.

\emph{3) Comparing methods:} Three traditional locating methods are implemented: 1) max likelihood; 2) least square; 3) weighted KNN. These three state-of-the-art locating methods need no offline training.
%The locating results of VOT are calculated and compared with max likelihood, least square and weighted KNN.


\emph{4) Categories of experiments:} Experiments are carried out in three categories: 1) Features of RSS data are analyzed, including stability of RSS difference and data correlation of wifipixes. 2) Locating robustness to phone conditions is evaluated, such as different types, inner status and placement of mobile phone. 3) General locating accuracy is evaluated in 18 different positions.
%One is to evaluate effect of phone conditions, such as different types, inner status and placement of mobile phone. It consists of two subparts, analyzing RSS data features under different phone conditions, and evaluate VOT's locating robustness to phone conditions and compare it with other three locating methods. %including different types, inner status and placement of  mobile phone.
%The second task is to evaluate locating accuracy of above 4 methods in 18 different positions.

%One significant obstacles for passive locating comes from the loud data noise and complicated condition of mobile phone. The data noise originates in various sources of electromagnetic interference or spacial shading. This noise can be rather huge due to low precision wifipix devices and mobile phone sensors. On the other hand,
\subsection{Data analysis}
There are several variables about phone conditions influencing the distribution of RSS data. We mainly consider three types of phone conditions to reduce difficulty of the experiment. They and their concrete values are set as follow.
\begin{itemize}
\item Type of mobile phone: $<$xiaomi, huawei, samsung, lenove$>$.%i.e. mobile phones from different companies.
\item Inner status of mobile phone: $<$scan, wifioff-screenoff, wifioff-screenon, wifion-screenon$>$. Wifion-screenoff is dropped as too little RSS signal can be captured under this inner status.%i.e. screen on or off, network on or off.
\item Placement of mobile phone: $<$inbag, inpocket, ondesk$>$.%i.e. on desk, in pocket or in bag.
\end{itemize}
%Several data analyses are conducted to investigate the influences on rss from above factors.
In the subsection, we evaluate stability of RSS difference and data correlation of wifipixes under different phone conditions.
20-minute RSS data is captured for the static smartphone under different phone conditions. The mean value of RSS for two specific wifipixes and their difference are plotted in Figure \ref{correlation of RSS}. %and the results are as follows.
%The correlated coefficients of under all phone conditions are
The correlated coefficients of wifipix, calculated by RSS data under all phone conditions, are in Table \ref{table of correlation}.
\begin{table}[!t]
%% increase table row spacing, adjust to taste
\renewcommand{\arraystretch}{1.3}
% if using array.sty, it might be a good idea to tweak the value of
% \extrarowheight as needed to properly center the text within the cells
\caption{Correlation coefficient among RSS of 6 wifipixes}
\label{table of correlation}
\centering
%% Some packages, such as MDW tools, offer better commands for making tables
%% than the plain LaTeX2e tabular which is used here.
\begin{tabular}{|c|c|c|c|c|c|c|}
\hline
wifipix & 1 & 2 & 3 & 4 & 5 & 6 \\
\hline
 1 & 1.0000  &  0.7226  &  0.6448  &  0.8134  &  0.6201  &  0.5303 \\
 \hline
 2 & 0.7226  &  1.0000  &  0.7741  &  0.7276  &  0.6250  &  0.6807 \\
 \hline
 3 & 0.6448  &  0.7741  &  1.0000  &  0.6586  &  0.4972  &  0.7384 \\
 \hline
 4 & 0.8134  &  0.7276  &  0.6586  &  1.0000  &  0.6179  &  0.5151 \\
 \hline
 5 & 0.6201  &  0.6250  &  0.4972  &  0.6179  &  1.0000  &  0.6576 \\
 \hline
 6 & 0.5303  &  0.6807  &  0.7384  &  0.5151  &  0.6576  &  1.0000 \\
 \hline
\end{tabular}
\end{table}
where the value in row $i$ and column $j$ is the correlated coefficient between RSS of wifipix $i$ and $j$.

From above figures, we can conclude that RSS differs when the mobile phone in different conditions. However, different RSS tends to have same shifting direction when condition changes. As a result, the ordinal relations of RSS among wifipixes are usually stable for different mobile phone conditions. Moreover, due to high noise of RSS, we can not transform RSS to distance with high precision by empirical formula, so the ordinal relations become valuable robust information from RSS data. %A smart way to make use of ordinal relations of RSS can provide very effective data clean and position estimation.

\subsection{Robustness VS variable phone conditions}
Locating robustness to different phone conditions is evaluated. We first generate 10 different phone states, made up by combination of above three phone conditions. One example of phone states is $<$xiaomi, scan, inbag$>$.
%we choose above 3 phone condtions
%inner status of mobile phone  $<$scan, wifioff-screenoff, wifioff-screenon, wifion-screenon$>$, 4 types of mobile phone $<$xiaomi, huawei, samsung, lenove$>$, and 3 placement  of mobile phone $<$inbag, inpocket, ondesk$>$
%to make up 10 different phone states.
Under each phone state, 20 minute RSS data of static smartphone is recorded.
%The phone is kept still for 20 minutes under each state, and its corresponding RSS data is recorded.
Then 20-minute RSS data is split into 40 groups, namely half-a-minute a group. Each position is estimated based on the mean RSS of the half-a-minute group. The overall locating result under 10 phone states is plotted in Figure \ref{CDF status}. Least square works worst and weighted KNN works second worst, whose average errors is about 1.5m. EK and max likelihood have many identical locating positions, as many ground truth positions are in constraints of EK. But EK works better than max likelihood in some extreme positions, and totally avoid overly terrible results. %We find VOT is more robust to state change.
%The experiments can be divided into two categories. First, we focus on evaluating robustness of OWKNN against dynamic factors, including device's difference, device's state difference and holding factors. The mobile phone is kept still for 20 minutes under one experiment set. And we split 20-minute RSS data into 10 groups, meaning 2 minutes a group. The experiment results are evaluated based on 2-minute RSS data.

\subsection{Accuracy VS variable positions}
General locating accuracy will be evaluated in 18 different positions.
%, which are distributed evenly chosen as ground truth in this office environment, which means averagely 1-2 positions are chosen in one office or corrider.
%The phone is required to stay still in each position for 10 minutes.
10-minute RSS data is recorded for each position. Then it is split into 20 half-a-minute groups. The locating positions of EK, max likelihood, least square and weighted KNN is estimated for each half-a-minute group.
 %The VOT's locating position for each group is calculated and compared with above 3 state-of-the-art methods.
 The general locating results is shown in Figure \ref{CDF position}. It shows that EK gives the most accurate locating result. We also find max likelihood works better than weighted KNN, A possible explanation of this is that the parameters of the empirical formula are set correctly, which is beneficial to max likelihood.

\section{Conclusion}
The paper proposes a robust system and investigate various usage of TOR in zero-calibrated passive indoor location. In our system, CF is used to fill the missing value and smooth the noise among RSS measurements firstly.
%TOR, used to eliminate positive correlated noise $E_1$, should be extracted and merged to bound the feasible region of user.
Then TORs are extracted, which characterize a feasible region in one snapshot, excluding the impact of positive correlated noises. 
To make use of TOR, a series of methods for smoothed feasible region mergence overtime have been investigated such as thresholding OCs in one snapshot, taking the intersection in multiple snapshots and smoothing by kernel and expansion. We show that smoothing method based on kernel and expansion can efficiently utilize the ordinal constraints overtime. Finally constrained nonlinear optimizations are proposed to estimate the location under TOR constraints.
%Methodologies based TOR have been investigated, which are SOC, MIROT and RSOT.
It is the first time that the potentials of TORs are systematically and comprehensively investigated and demonstrated  for accurate and robust passive locating.
% A simple method to narrow down the feasible region is bounding $R_t$ by thresholding OCs. But this method can easily fall into the dilemma of reliability and accuracy depending on the selection of $T_h$. %but $R_t$ is often too large to assist future optimization.
% The direct intersection area of $R_t$ of successive snapshots also can give the feasible region to assist future optimization. But the intersection area can be empty or separated.
% Smoothed mergence algorithms considering target movement are also investigated. For such algorithms, $R_{t+1}$ should be contained in $R_t'$, the expansion of $R_t$, and contain $R_t''$, the kernel of $R_t$. Modified OCs in time $t+1$ should be incorporated into $R_t'$ to characterize $R_{t+1}$.
%%MIROT bounds maximum intersection region $R_t$ constructed by OCs during window $T$, but $R_t$ often cannot change continuously over time. RSOT maintain continuous changing $R_t$ with the proper size by prolonging region expansion and comprise of OCs.
% We finally use a constrained nonlinear optimization model to calculate the position of user in feasible region $R_t$.

The proposed smoothed ordinal constraint method is verfied by extensive simulations and practical experiments, showing the smoothing by kernel and expansion provides reliable and accurate results compared with various zero-calibrated passive locating algorithms. Above features prove the validity of TOR in practical passive locating. In future work, we will explore other constrained location algorithms based on TOR and fuse them with particle filter and digital floor map information. These constrained location algorithms algorithms can also be applied to other locating systems, such as bluetooth based locating system etc.


% conference papers do not normally have an appendix


% use section* for acknowledgment
%\section*{Acknowledgment}


%The authors would like to thank...





% trigger a \newpage just before the given reference
% number - used to balance the columns on the last page
% adjust value as needed - may need to be readjusted if
% the document is modified later
%\IEEEtriggeratref{8}
% The "triggered" command can be changed if desired:
%\IEEEtriggercmd{\enlargethispage{-5in}}

% references section

% can use a bibliography generated by BibTeX as a .bbl file
% BibTeX documentation can be easily obtained at:
% http://mirror.ctan.org/biblio/bibtex/contrib/doc/
% The IEEEtran BibTeX style support page is at:
% http://www.michaelshell.org/tex/ieeetran/bibtex/
%\bibliographystyle{IEEEtran}
% argument is your BibTeX string definitions and bibliography database(s)
%\bibliography{IEEEabrv,../bib/paper}
%
% <OR> manually copy in the resultant .bbl file
% set second argument of \begin to the number of references
% (used to reserve space for the reference number labels box)
\bibliographystyle{IEEEtran}
\bibliography{bare_conf.bib}




% that's all folks
\end{document}


